package com.example.hot100;

import java.util.Arrays;

/**
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 *
 *  示例 1：
 * 输入：n = 2
 * 输出：[0,1,1]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 *
 *  示例 2：
 * 输入：n = 5
 * 输出：[0,1,1,2,1,2]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 3 --> 11
 * 4 --> 100
 * 5 --> 101
 */
public class Leetcode338_CountBits {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().countBits(5)));
    }

    static class Solution {
        /**
         * 动态规划
         * @param n
         * @return
         */
        public int[] countBits3(int n) {
            int[] dp = new int[n + 1];
            int highBit = 0; // 用于记录最高有效位
            for (int i = 1; i <= n; i++) {
                if ((i & (i - 1)) == 0) { // i 为 2的整数幂才会等于0
                    highBit = i;
                }

                dp[i] = dp[i - highBit] + 1;
            }
            return dp;
        }

        /**
         * Brian Kernighan算法:一位一位算
         *  num & (num − 1)，该运算将 num 的二进制表示的最后一个 1 变成 0
         * @param n
         * @return
         */
        public int[] countBits2(int n) {
            int[] res = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                int tmp = i;
                int count = 0;
                while (tmp > 0) {
                    tmp = tmp & (tmp - 1); // num & (num − 1)，该运算将 num 的二进制表示的最后一个 1 变成 0
                    ++count;
                }
                res[i] = count;
            }
            return res;
        }

        /**
         * 暴力法，一个数一个数的算"1"的位数
         * @param n
         * @return
         */
        public int[] countBits1(int n) {
            int[] res = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                int tmp = i;
                int count = 0;
                while (tmp > 0) {
                    if ((tmp & 1) == 1) {
                        ++count;
                    }
                    tmp = tmp >> 1;
                }
                res[i] = count;
            }
            return res;
        }

        public int[] countBits(int n) {
            return countBits3(n);
        }
    }
}
